package com.zjj.learn.algorithmPlus.segment2.binaryTree;

/**
 * 二叉线索树
 *
 * @author zjj_admin
 */
public class BSTTree<K extends Comparable<K>, V> {

    public BSTNode<K, V> root;

    public BSTTree(BSTNode<K, V> root) {
        this.root = root;
    }


    /**
     * 前序遍历，继续递归实现
     *
     * @param root
     */
    public static void preOrder(BSTNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.key + "\t");
        preOrder(root.left);
        preOrder(root.right);
    }

    /**
     * 根据线索二叉树的键获取值
     * 使用递归的思想
     *
     * @param key 线索二叉树的键
     * @return 值
     */
    public V get1(K key) {
        return doGet(root, key);
    }

    /**
     * 递归调用
     *
     * @param node
     * @param key
     * @return
     */
    private V doGet(BSTNode<K, V> node, K key) {
        if (node == null) {
            return null;
        }
        //递归遍历
        int result = key.compareTo(node.key);
        if (result < 0) {
            return doGet(node.left, key);
        } else if (result > 0) {
            return doGet(node.right, key);
        } else {
            return node.data;
        }
    }

    /**
     * 使用非递归的思路获取二叉线索树的 key 对应的值
     *
     * @param key
     * @return
     */
    public V get2(K key) {
        BSTNode<K, V> p = root;
        while (p != null) {
            int compare = key.compareTo(p.key);
            if (compare < 0) {
                p = p.left;
            } else if (compare > 0) {
                p = p.right;
            } else {
                return p.data;
            }
        }
        return null;
    }

    /**
     * 查找二叉线索树的最小关键字的值
     *
     * @return 键最小对应的值
     */
    public V min() {
        if (root == null) {
            return null;
        }
        return min(root).data;
    }


    /**
     * 查找二叉线索树的最大关键字的值
     *
     * @return 键最大对应的值
     */
    public V max() {
        if (root == null) {
            return null;
        }
        return max(root).data;
    }

    private BSTNode<K, V> max(BSTNode<K, V> node) {
        if (node == null) {
            throw new NullPointerException("node 为 null...");
        }
        BSTNode<K, V> p = node;
        //依次向左下方遍历即可
        while (p.right != null) {
            p = p.right;
        }
        return p;
    }

    /**
     * 获取一个节点的最小节点
     *
     * @param node
     * @return
     */
    private BSTNode<K, V> min(BSTNode<K, V> node) {
        if (node == null) {
            throw new NullPointerException("node 为 null...");
        }
        BSTNode<K, V> p = node;
        //依次向左下方遍历即可
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }

    /**
     * 添加数据，当 key 不存在时就添加，存在就修改
     * 此方法和 Java 中的 HashMap 的 put 方法时类似的
     *
     * @param key
     * @param data
     */
    public void put(K key, V data) {
        BSTNode<K, V> node = root;
        BSTNode<K, V> parent = node;
        //判断 key 的节点是否存在，存在就直接修改，不存在就根据 parent 添加
        while (node != null) {
            //修改当前节点的父节点
            parent = node;
            int compare = key.compareTo(node.key);
            if (compare < 0) {
                node = node.left;
            } else if (compare > 0) {
                node = node.right;
            } else {
                //这里需要更新
                node.data = data;
                return;
            }
        }
        //这里需要添加数据
        if (parent == null) {
            root = new BSTNode<>(key, data);
            return;
        }
        if (key.compareTo(parent.key) < 0) {
            // 向 parent 的左节点添加
            parent.left = new BSTNode<>(key, data);
        } else {
            // 向 parent 的右节点添加
            parent.right = new BSTNode<>(key, data);
        }
    }

    /**
     * 获取每一个节点 key 的前任节点
     * 将二插搜索数按照中序遍历，一个节点的前一个节点就是当前节点的前驱节点
     * <p>
     * <p>
     * -        4
     * -    2          7
     * -  1   3      6     8
     * -           5
     * <p>
     * 分情况：
     * 1、当一个节点有左子树时，此时当前节点的前驱节点就是左子树的最大值
     * 2、节点没有左子树时。
     * --- 若最近的祖先是从左边来的，这个祖先即为前驱节点，例如 5 的前任时 4 。
     *
     * @return
     */
    public BSTNode<K, V> predecessor(K key) {
        //首先需要找到 key 为所给数据的节点
        BSTNode<K, V> p = root;
        BSTNode<K, V> ancestorFromLeft = null;
        while (p != null) {
            int compare = key.compareTo(p.key);
            if (compare < 0) {
                p = p.left;
            } else if (compare > 0) {
                //表示当前 p 是从左边来的祖先
                ancestorFromLeft = p;
                p = p.right;
            } else {
                break;
            }
        }
        //找到了已知节点
        if (p == null) {
            return null;
        }
        //节点的左节点不为 null 时，返回左节点的最大值key
        if (p.left != null) {
            return max(p.left);
        }
        //当左节点 null 时，返回最近从左侧来的祖先
        return ancestorFromLeft;
    }

    /**
     * 获取某一个节点 key 的后任节点
     * <p>
     * 分情况：
     * 1、当节点有右子树时，后继节点就是右子树的最小值
     * 2、当没有右子树时，找自右而来最近的祖先，例如在上面前驱节点的例子中。 3 的第一个自右而来的祖先是 4
     *
     * @return
     */
    public BSTNode<K, V> successor(K key) {
        //首先需要找到 key 为所给数据的节点
        BSTNode<K, V> p = root;
        BSTNode<K, V> ancestorFromRight = null;
        while (p != null) {
            int compare = key.compareTo(p.key);
            if (compare < 0) {
                //表示当前 p 是从右边来的祖先
                ancestorFromRight = p;
                p = p.left;
            } else if (compare > 0) {
                p = p.right;
            } else {
                break;
            }
        }
        //找到了已知节点
        if (p == null) {
            return null;
        }
        if (p.right != null) {
            return min(p.right);
        }
        //当左节点 null 时，返回最近从右侧来的祖先
        return ancestorFromRight;
    }


    /**
     * 删除指定 key 的节点
     *
     * @param key 指定 key
     * @return 删除的节点
     */
    public BSTNode<K, V> remove(K key) {
        BSTNode<K, V> curr = root;
        // 父节点
        BSTNode<K, V> parent = null;
        while (curr != null) {
            int compare = key.compareTo(curr.key);
            if (compare < 0) {
                parent = curr;
                curr = curr.left;
            } else if (compare > 0) {
                parent = curr;
                curr = curr.right;
            } else {
                break;
            }
        }
        //当指定的 key 不存在时，直接返回即可
        if (curr == null) {
            return null;
        }
        //删除节点
        remove(parent, curr);
        return curr;
    }

    /**
     * 删除节点
     *
     * @param parent  待删除节点的父节点
     * @param removed 待删除的节点
     */
    @SuppressWarnings("all")
    private void remove(BSTNode<K, V> parent, BSTNode<K, V> removed) {
        // 1、当被删除节点的两个子节点都为 null 时
        if (removed.left == null && removed.right == null) {
            if (parent.left == removed) {
                parent.left = null;
            } else {
                //当被删除节点为父节点的右节点时
                parent.right = null;
            }
            return;
        }
        // 2、当被删除节点的左节点为 null，右节点不为 null 时
        if (removed.left == null && removed.right != null) {
            //当被删除节点为父节点的左节点时
            if (parent.left == removed) {
                parent.left = removed.right;
                removed.right = null;
            } else {
                //当被删除节点为父节点的右节点时
                parent.right = removed.right;
                removed.right = null;
            }
            return;
        }
        // 3、当被删除节点的右节点为 null ，左节点不为 null 时
        if (removed.left != null && removed.right == null) {
            //当被删除节点为父节点的左节点时
            if (parent.left == removed) {
                parent.left = removed.left;
                removed.right = null;
            } else {
                //当被删除节点为父节点的右节点时
                parent.right = removed.left;
                removed.right = null;
            }
            return;
        }
        //4、当被删除节点的左节点和右节点都不为 null 时
        if (removed.left != null && removed.right != null) {
            //找到被删除节点的后继节点
            BSTNode<K, V> houji = removed.right;
            //后继节点的父节点
            BSTNode<K, V> houjiParent = houji;
            while (houji.left != null) {
                houjiParent = houji;
                houji = houji.left;
            }
            //当后继节点和被删除节点相邻时
            if (houjiParent == houji) {
                // 使用后继节点替换被删除节点即可
                removed.data = houji.data;
                removed.key = houji.key;
                //后继节点不可能有左子节点，这是由线索二叉树的性质决定的
                removed.right = houji.right;
            } else {
                //被删除节点的值就是后继节点
                removed.data = houji.data;
                removed.key = houji.key;
                //删除后继节点
                remove(houjiParent, houji);
            }
        }
    }

}
